
#include "List.h"
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stddef.h>

	typedef struct _LIST_ENTRY
	{
		struct _LIST_ENTRY *Flink;
		struct _LIST_ENTRY *Blink;
	} LIST_ENTRY, *PLIST_ENTRY;
//point to self
#define InitializeListHead(ListHead) (\
	(ListHead)->Flink = (ListHead)->Blink = (ListHead))

#define IsListEmpty(ListHead) \
	((ListHead)->Flink == (ListHead))
//remove the item before ListHead
#define RemoveHeadList(ListHead) \
    (ListHead)->Flink;\
    {RemoveEntryList((ListHead)->Flink)}
//remove the item after ListHead
#define RemoveTailList(ListHead) \
    (ListHead)->Blink;\
    {RemoveEntryList((ListHead)->Blink)}
//remove Entry item
#define RemoveEntryList(Entry) {\
    PLIST_ENTRY _EX_Blink;\
    PLIST_ENTRY _EX_Flink;\
    _EX_Flink = (Entry)->Flink;\
    _EX_Blink = (Entry)->Blink;\
    _EX_Blink->Flink = _EX_Flink;\
    _EX_Flink->Blink = _EX_Blink;\
    }
//insert after ListHead
#define InsertTailList(ListHead,Entry) {\
    PLIST_ENTRY _EX_Blink;\
    PLIST_ENTRY _EX_ListHead;\
    _EX_ListHead = (ListHead);\
    _EX_Blink = _EX_ListHead->Blink;\
    (Entry)->Flink = _EX_ListHead;\
    (Entry)->Blink = _EX_Blink;\
    _EX_Blink->Flink = (Entry);\
    _EX_ListHead->Blink = (Entry);\
    }
//insert before ListHead
#define InsertHeadList(ListHead,Entry) {\
    PLIST_ENTRY _EX_Flink;\
    PLIST_ENTRY _EX_ListHead;\
    _EX_ListHead = (ListHead);\
    _EX_Flink = _EX_ListHead->Flink;\
    (Entry)->Flink = _EX_Flink;\
    (Entry)->Blink = _EX_ListHead;\
    _EX_Flink->Blink = (Entry);\
    _EX_ListHead->Flink = (Entry);\
    }



typedef struct _ListItem
{
	LIST_ENTRY	entry;
	void*		data;
} ListItem;

struct _List
{
	LIST_ENTRY	entry;			//list head
	//int			size;			//item size
	int			count;			//item count
	void* (*alloc)(size_t);
	void (*free)(void*);
	void (*destruct)(void*);
};

/* Create and free									*/
List* List_create() {
	List* list = (List*)malloc(sizeof(List));
	memset(list, 0, sizeof(List));
	InitializeListHead(&list->entry);
	list->count = 0;
	list->alloc = malloc;
	list->free = free;
	return list;
}

void List_free(List* list) {
	if (list){
		List_clear(list);
		free(list);
	}
}

/* Status                                           */
int List_count(List* list) {
	if (list)
		return list->count;
	return 0;
}

BOOL List_empty(List* list) {
	if (list)
		return IsListEmpty(&list->entry);
	return TRUE;
}

/* Head/Tail Access                                 */
void* List_head(List* list) {
	if (list && (list->entry.Flink != &list->entry))
		return ((ListItem*)(list->entry.Flink))->data;
	return NULL;
}

void* List_tail(List* list) {
	if (list && (list->entry.Blink != &list->entry))
		return ((ListItem*)(list->entry.Blink))->data;
	return NULL;
}

/* Operations                                       */
//remove the head of the list
void*        List_removeHead(List* list) {
	void* result = NULL;
	if (list && !IsListEmpty(&list->entry)) {
		LIST_ENTRY* p = RemoveHeadList(&list->entry);
		result = ((ListItem*)p)->data;
		if (list->destruct)
			list->destruct(result);
		list->free(p);
		list->count--;
	}
	return result;
}

void*        List_removeTail(List* list) {
	void* result = NULL;
	if (list && !IsListEmpty(&list->entry)) {
		LIST_ENTRY* p = RemoveTailList(&list->entry);
		result = ((ListItem*)p)->data;
		if (list->destruct)
			list->destruct(result);
		list->free(p);
		list->count--;
	}
	return result;
}

ListPosition List_addHead(List* list, const void* newElement) {
	ListPosition result = NULL;
	if (list){
		ListItem* item = (ListItem*)list->alloc(sizeof(ListItem));
		item->data = (void*)newElement;

		InsertHeadList(&list->entry, &item->entry);
		list->count++;
		result = (ListPosition)item;
	}
	return result;
}

ListPosition List_addTail(List* list, const void* newElement) {
	ListPosition result = NULL;
	if (list){
		ListItem* item = (ListItem*)list->alloc(sizeof(ListItem));
		item->data = (void*)newElement;

		InsertTailList(&list->entry, &item->entry);
		list->count++;
		result = (ListPosition)item;
	}
	return result;
}

void         List_clear(List* list) {
	if (list) {
		int i = 0;
		int count = list->count;
		while(!IsListEmpty(&list->entry)){
			List_removeTail(list);
			i++;
		}
		list->count = 0;
		InitializeListHead(&list->entry);
		if (i != count){
			assert(0);
		}
	}
}

/* Iteration                                        */
ListPosition List_headPosition(List* list) {
	if (list && (list->entry.Flink != &list->entry))
		return (ListPosition)list->entry.Flink;
	return NULL;
}

ListPosition List_tailPosition(List* list) {
	if (list && (list->entry.Blink != &list->entry))
		return (ListPosition)list->entry.Blink;
	return NULL;
}

void*		List_next(List* list, ListPosition* pp) {
	void* value = NULL;
	if (list && pp && *pp){
		//get current value;
		value = ((ListItem*)(*pp))->data;
		//next
		*pp = ((LIST_ENTRY*)(*pp))->Flink;
		if (*pp == &list->entry)
			*pp = NULL;
	}
	return value;
}

void*		List_prev(List* list, ListPosition* pp) {
	void* value = NULL;
	if (list && pp && *pp){
		//get current value;
		value = ((ListItem*)(*pp))->data;
		//back
		*pp = ((LIST_ENTRY*)(*pp))->Blink;
		if (*pp == &list->entry)
			*pp = NULL;
	}
	return value;
}

/* Retrieval/Modification                           */
void*        List_get(List* list, ListPosition p) {
	return ((ListItem*)p)->data;
}

void         List_set(List* list, ListPosition p, const void* newElement) {
	((ListItem*)p)->data = (void*)newElement;
}

void         List_remove(List* list, ListPosition p) {
	if (list && !IsListEmpty(&list->entry)){
		RemoveEntryList((LIST_ENTRY*)p);
		list->count--;
		if (list->destruct)
			list->destruct(((ListItem*)p)->data);
		list->free(p);
	}
}

/* Insertion                                        */
ListPosition List_insertBefore(List* list, ListPosition p, const void* newElement) {
	if (list){
		ListItem* item = (ListItem*)list->alloc(sizeof(ListItem));
		item->data = (void*)newElement;

		InsertTailList((LIST_ENTRY*)p, (LIST_ENTRY*)item);
		list->count++;
		return (LIST_ENTRY*)item;
	}
	return NULL;
}

ListPosition List_insertAfter(List* list, ListPosition p, const void* newElement) {
	if (list){
		ListItem* item = (ListItem*)list->alloc(sizeof(ListItem));
		item->data = (void*)newElement;

		InsertHeadList((LIST_ENTRY*)p, (LIST_ENTRY*)item);
		list->count++;
		return (LIST_ENTRY*)item;
	}
	return NULL;
}

/* Searching                                        */
ListPosition List_find(List* list, const void* searchValue) {
	if (list){
		LIST_ENTRY* pListHead = &list->entry;
		LIST_ENTRY* pEntry = pListHead->Flink;

		for (; pEntry != pListHead; pEntry = pEntry->Flink ) {
			if (searchValue == ((ListItem*)(pEntry))->data) {
				return pEntry;
			}
		}
	}
	return NULL;
}

ListPosition List_findEx(List* list, const void* searchValue, ListPosition startAfter,
						int (*compare)(const void*, const void*)) {
	if (list){
		LIST_ENTRY* pListHead = &list->entry;
		LIST_ENTRY* pEntry = (LIST_ENTRY*)startAfter;

		for (; pEntry != pListHead; pEntry = pEntry->Flink ) {
			if (0 == compare(searchValue, ((ListItem*)(pEntry))->data)) {
				return pEntry;
			}
		}
	}
	return NULL;
}


ListPosition List_findIndex(List* list, int index) {
	LIST_ENTRY* result = 0;
	if (list){
		int i;

		result = list->entry.Flink;
		for (i=0; i<index; ++i){
			result = result->Flink;
		}
	}
	return (ListPosition)result;
}


/* Helper											*/
void List_destructor(List* me, void (*destructFun)(void*)) {
	if (me)
		me->destruct = destructFun;
}


